package com.dx.VegetableOxygenBarBackEnd.utils;

import java.util.List;
import java.util.Objects;

/**
 * 算法工具类
 */
public class AlgorithmUtils {
    /**编辑距离算法
     * 用于：寻找最相似列表
     *
     * @param tagList1
     * @param tagList2
     * @return
     */
    public static int minDistance(List<String> tagList1, List<String> tagList2) {
        int n = tagList1.size();
        int m = tagList2.size();
        // If either string is empty, the edit distance is the length of the other string
        if (n * m == 0)
            return n + m;
        // Create a DP table of size (n+1) x (m+1)
        int[][] d = new int[n + 1][m + 1];
        // Initialize the first column (transforming word1 into an empty string)
        for (int i = 0; i <= n; i++) {
            d[i][0] = i;
        }
        // Initialize the first row (transforming an empty string into word2)
        for (int j = 0; j <= m; j++) {
            d[0][j] = j;
        }
        // Fill in the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int left = d[i - 1][j] + 1; // Deletion
                int down = d[i][j - 1] + 1; // Insertion
                int left_down = d[i - 1][j - 1]; // No change (if characters match)
                // If characters don't match, add 1 to the substitution cost
                if (!Objects.equals(tagList1.get(i - 1), tagList2.get(j - 1)))
                    left_down += 1;
                // Take the minimum of the three possible operations
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        // The answer is the minimum edit distance between word1 and word2
        return d[n][m];
    }
    /**编辑距离算法
     * 用于：寻找最相似字符串
     *
     * @param word1
     * @param word2
     * @return
     */
    public static int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        // If either string is empty, the edit distance is the length of the other string
        if (n * m == 0)
            return n + m;
        // Create a DP table of size (n+1) x (m+1)
        int[][] d = new int[n + 1][m + 1];
        // Initialize the first column (transforming word1 into an empty string)
        for (int i = 0; i <= n; i++) {
            d[i][0] = i;
        }
        // Initialize the first row (transforming an empty string into word2)
        for (int j = 0; j <= m; j++) {
            d[0][j] = j;
        }
        // Fill in the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int left = d[i - 1][j] + 1; // Deletion
                int down = d[i][j - 1] + 1; // Insertion
                int left_down = d[i - 1][j - 1]; // No change (if characters match)
                // If characters don't match, add 1 to the substitution cost
                if (word1.charAt(i - 1) != word2.charAt(j - 1))
                    left_down += 1;
                // Take the minimum of the three possible operations
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        // The answer is the minimum edit distance between word1 and word2
        return d[n][m];
    }

}
